1. Field of the Invention
The present invention relates to congestion control in a network and more particularly to Active Queue Management based on desired queue occupancy.
2. Description of Related Art
With the proliferation of internet and data communications, communication networks are being used to carry an increasing amount of traffic. At the same time, user expectations for network speed and reliability are also increasing.
In a packet network such as the Internet for example, packets of information are conveyed between a packet source and a packet sink. The source may be any device that transmits data on the network and the sink may be any device that receives data from a network. Typically, a sink will send an acknowledgement signal to a source of a packet to indicate that a packet has been received.
Between a source and a sink, data packets pass through intermediate elements on the network, for example routers, switches and gateways, which receive and queue data packets for transmission on one or more communications channels. To avoid overloading any given channel, packet transmission on each channel must be managed and controlled.
One technique for managing traffic on a network is to control transmissions from the sources. Typically, a source will have a packet queue and the rate at which packets are transmitted from the packet queue is determined by a sliding window operating on the packet queue, which prevents the source from transmitting a new packet onto the network whenever more than a specified number of transmitted packets remain unacknowledged by the corresponding sink. Each time a transmitted packet is acknowledged by the sink, the window advances, permitting the source to transmit a new packet onto the network. The size of the window may be varied by the source, depending on the capacity of the channel and the ability of the sink to accept packets. These two factors are measured by receiving acknowledgements at the source. Generally if acknowledgements are received, the rate of transmission is increased by increasing the size of the window and if acknowledgements are not received or duplicate acknowledgements are received, i.e. packet loss is occurring, then the rate of transmission is decreased by decreasing the size of the window. Hence, there exists a relationship in which packet loss causes a packet source to reduce its transmission rate, which in turn reduces network congestion.
Effectively, the rate at which a source provides packets to the network is dependent upon receiving acknowledgements. An important consequence of this relationship is that an intermediate network element can intentionally discard or drop packets to prevent them from reaching the sink, thereby eliminating any acknowledgement back to the source, resulting in the source failing to receive an acknowledgement, in which case it reduces its window size and packet transmission rate. In this manner, an intermediate network element can change packet transmission rates of any source from which it receives packets.
This intentional discarding or dropping of packets is referred to as active queue management. Using this technique, the intermediate element responds to increasing traffic by selectively dropping packets from a queue of the intermediate element well before the queue overflows, causing the sources of the dropped packets to reduce their transmission rates to ease queue congestion.
One form of active queue management is Random Early Detection (RED). A RED queue manager maintains a weighted average of the queue length and detects when the average queue length increases beyond a threshold. In response, it causes randomly selected packets to be dropped from the queue. The act of dropping randomly selected packets from the queue is spaced out in time to cause only some sources to decrease transmission rate while other sources continue to send packets at their previous rates.
The probability that a packet arriving at the queue is dropped depends on, among other things, the average queue length, the time elapsed since the last packet was dropped, and a maximum drop probability parameter. However, the weighting that each of these factors has on the probability of being dropped depends on network conditions including the number of active source-sink pairs (xe2x80x9cconnectionsxe2x80x9d), for example. Consequently the probability that a packet will be dropped changes as network conditions change, resulting in a less than optimal packet drop probability over a wide range of network conditions.
Thus, there is a need for a queue management technique that can make optimum use of a queue by randomly discarding packets with an optimal drop probability that reflects network conditions to better utilize the queue. Additionally, it would be desirable for the technique to make optimum use of the queue without the need to estimate a number of active network connections to the queue and without collecting or analyzing state information on individual connections.
The present invention addresses the above needs by providing an apparatus and method for controlling a rate at which packets are transmitted to a network element having a queue, involving generating a probability value in response to queue occupancy and desired queue occupancy and controlling the packet in response to the probability value and a reference value to cause a source of the packet to change its transmission rate. Advantageously, this arrangement can be applied over a wide range of load levels and, network conditions and stabilizes queue occupancy at a level independent of the number of active network connections.
Generating the probability value preferably includes generating a current error value in response to the queue occupancy and the desired queue occupancy. In particular, the current error value may be time-filtered to produce a filtered current error value. Such filtering might be accomplished through producing a weighted sum of present and past current error values. This arrangement is desirable because data transmissions generally include uneven bursts of data and as a result, the amount of data stored in a queue may fluctuate significantly. The filtered current error value may further be weighted as a function of a pre-defined control gain factor and queue capacity and the probability value may be calculated as a function of the filtered current error value and a previous probability value.
In one embodiment, the reference value may be a random number generated by a random number generator.
In one embodiment a controller controls admission of the packet into the queue in response to the probability value and the reference value. More particularly, the probability value is compared to the reference value, and if the probability value is greater than or equal to the reference value then the packet is discarded, otherwise the packet is admitted into the queue.
In a variation of the above embodiment, an inter-drop/mark value, representing a number of packets to be accepted into the queue between dropped or marked packets, is generated as a function of the drop probability value and admission of a packet to the queue or marking of a packet is controlled in response to the inter-drop/mark value. In particular, the inter-drop/mark value may be generated as the floor of the reciprocal of the probability value. Use of the inter-drop/mark value to admit or reject packets permits a specific probability, for example 25%, to be achieved by regularly dropping packets or marking packets, for example every fourth packet arriving at the queue. In such an embodiment, the reference value used by the controller may be generated by producing a representation of a count of packets arriving at the queue. The admission of a packet into the queue or marking of a packet may be controlled in response to the probability value in the form of an inter-drop/mark value and the reference value in the form of a count. More particularly, the inter-drop/mark value may be compared to the reference value, and if the inter-drop/mark value is less than or equal to the count then the packet is discarded, or marked, otherwise it is admitted into the queue.
Where the controller causes the packet to be marked, the packet is modified to include a congestion notification message for receipt by the sink, rather than dropping the packet. The congestion notification message is to inform the sink that congestion was experienced somewhere along the communication channel. For example, a header of the packet may be modified to include such a message. When the sink receives a packet with the congestion notification message (that is, a xe2x80x9cmarked packetxe2x80x9d), the sink sends an acknowledgement to the source with the acknowledgement modified to include a congestion notification message. In this manner, the net effect at the source is that an acknowledgement including a congestion notification message is received, and in response, the source reduces its transmission rate. This embodiment provides the benefit that the packet is not dropped, but rather is received by the sink.
Effectively, by causing arriving packets to be dropped or marked in response to a probability calculated in response to queue occupancy and desired queue occupancy, the probability continually changes depending on the status of the queue. Consequently, the probability that a sink will not send an acknowledgement or alternatively, that a sink will send an acknowledgement carrying a congestion notification message to the source also changes, resulting in a corresponding change in transmission rate of the source. Thus the flow of packets is better controlled in the sense that the queue is less likely to overflow or be under-utilized. Effectively, packets are dropped or marked as necessary to urge the queue occupancy level toward a desired queue occupancy level under a wide range of network conditions. A queue having a queue occupancy level stabilized about a desired queue occupancy level provides higher resource utilization, predictable delays, more certain buffer provisioning, and load-independent performance. These benefits may be achieved without the need to estimate a number of active network connections to the queue and without collecting or analyzing state information on individual connections.
Other aspects and features of the present invention will become apparent to those ordinarily skilled in the art upon review of the following description of specific embodiments of the invention in conjunction with the accompanying figures.